﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.GreedyCode
{
    class Medium
    {
        //============================================力扣376 摆动序列
        //如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
        //子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
        //给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
        public int WiggleMaxLength(int[] nums)
        {
            if (nums.Length <= 1)
                return nums.Length;

            int curDiff = 0;//当前一对差值
            int preDiff = 0;//前一对差值
            int result = 1;//记录峰值个数，序列默认序列最右边有一个峰值
            for (int i = 0; i < nums.Length - 1; i++)
            {
                curDiff = nums[i + 1] - nums[i];
                //出现峰值
                if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0))
                {
                    result++;
                    preDiff = curDiff;
                }
            }
            return result;
        }

        //==================================力扣135 分发汤锅
        //老师想给孩子们分发糖果，有N个孩子站成一排，老师会根据每个孩子的表现，预先给他们评分。
        //你需要按照以下要求，帮助老师给这些孩子分发糖果：
        //每个孩子至少分配到 1 个糖果。
        //评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
        //那么这样下来，老师至少需要准备多少颗糖果呢？
        public int Candy(int[] ratings)
        {//思路：先确定右边评分大于左边的情况（也就是从前向后遍历）
            //局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果

            int[] CandyVec = new int[ratings.Length];

            CandyVec[0] = 1;
            for(int i = 1;i<ratings.Length;i++)
            {
                if (ratings[i] > ratings[i - 1])
                    CandyVec[i] = CandyVec[i - 1] + 1;
                else
                    CandyVec[i] = 1;

            }

            //再确定左孩子大于右孩子的情况（从后向前遍历）
            for(int i = ratings.Length-2;i>=0;i--)
            {
                if (ratings[i] > ratings[i + 1])
                    CandyVec[i] = Math.Max(CandyVec[i], CandyVec[i + 1] + 1);
            }

            int result = 0;
            foreach (int i in CandyVec)
                result += i;
            return result;
        }

        //=======================================力扣406 根据身高重建队列
        //假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）
        //每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。.
        //请你重新构造并返回输入数组 people 所表示的队列。
        //返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
        public int[][] ReconstructQueue(int[][] people)
        {//遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。
            //局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
            //全局最优：最后都做完插入操作，整个队列满足题目队列属性

            for(int i = 0; i<people.Length;i++)
            {
                for(int j = i+1;j<people.Length;j++)
                {
                    if((people[i][0] < people[j][0])|| (people[i][0] == people[j][0] && people[i][1] < people[j][1]))
                    {
                        int[] tmp = people[i];
                        people[i] = people[j];
                        people[j] = tmp;
                    }
                }
            }

            List<int[]> que = new List<int[]>();
            for(int i = 0;i<people.Length;i++)
            {
                int position = people[i][1];
                que.Insert(position, people[i]);
            }
            return que.ToArray();
        }

        //================================================kill738 单调递增的数字
        //给定一个非负整数N。找出小于或等于N的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增的
        //当且仅当每个相邻位数上的数字x和y满足x<=y时，我们称这个整数时单调递增的
        public int MonotoneIncreasingDigits(int n)
        {
            //局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
            //全局最优：得到小于等于N的最大单调递增的整数。
            //从前后向遍历会改变已经遍历过的结果！
            //所以最好从后向前遍历

            string strNum = n.ToString();
            char[] arr = strNum.ToCharArray();

            // flag用来标记赋值9从哪里开始
            // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
            int flag = arr.Length;
            for(int i = arr.Length-1;i>0;i--)
            {
                if(arr[i-1] > arr[i])
                {
                    flag = i;
                    arr[i - 1]--;
                }
            }
            for(int i = flag;i<arr.Length;i++)
            {
                arr[i] = '9';
            }
            strNum = new string(arr);

            return int.Parse(strNum);
        }

    }
}
